#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int tmp[50010];
    int reversePairs(vector<int>& nums) {
        return mergesort(nums, 0, nums.size() - 1);
    }

    int mergesort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return 0;

        int mid = (right + left) >> 1;
        int ret = 0;

        ret += mergesort(nums, left, mid);
        ret += mergesort(nums, mid + 1, right);

        int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid)
        {
            while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;
            if (cur2 > right) break;
            ret += right - cur2 + 1;
            cur1++;
        }

        cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
        {
            if (nums[cur1] <= nums[cur2])
            {
                tmp[i++] = nums[cur2++];
            }
            else
            {
                tmp[i++] = nums[cur1++];
            }
        }

        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];

        for (int i = left;i <= right;i++)
        {
            nums[i] = tmp[i - left];
        }

        return ret;
    }
};